package 零钱兑换II;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/10 14:35
 * @description:
 */
public class Solution2 {
    public int change(int amount, int[] coins) {
        // 完全背包问题
        // ① dp数组及其含义：dp[i]表示金额为i时，从coins可以选择的硬币中选择硬币，选取方案的最大值
        // ② 状态转移方程：dp[i] = dp[i] + dp[i][j-coins[i]];
        //                      最大方案数 = 不包含coins[i]的最大方案数 + 包含coins[i]的最大方案数
        // ③ dp数组初始化：dp[0] = 1
        // ④ 遍历顺序：先遍历coins，再遍历amount(从大到小，还是从小到大遍历是有讲究的)
        // ⑤ 举例推导dp数组：amount = 5, coins = [1, 2, 5]
        //              index:      0   1   2   3   4   5
        //                          1   1   1   1   1   1
        //                          1   1   2   2   3   3
        //                          1   1   2   2   3   4

        int[] dp = new int[amount + 1];
        dp[0] = 1;
        // 这里有讲究了，先遍历硬币，再遍历背包 ==>
        // 求的是组合数（比如coins[0] = 1，coins[1] = 5，那么就是先考虑1在考虑5，最后方案只会出现{1，5}这种情况，而不会出现{5，1}）
        // 如果是先遍历背包，再遍历硬币 ==>
        // 求的是排列数（比如coins[0] = 1，coins[1] = 5，每一个背包的容量值，都是经历过1，5计算的！会出现{1,5},{5,1}这两种情况）
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
//            System.out.println(Arrays.toString(dp));
        }

        /*for (int i = 0; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i >= coins[j]){
                    dp[i] = dp[i] + dp[i - coins[j]];
                }
            }
            System.out.println(Arrays.toString(dp));
        }*/

        return dp[amount];
    }
}
